package com.mjx.algorithm;

import com.mjx.algorithm.tool.Tools;

/**
 * 希尔排序：根据序列公式，先从大的间隔排序，直至间隔为1，为1就是插入排序
 * 效率O(N3/2)~O(N7/6)
 * Created by meijingxiang on 2017/2/3.
 */
public class ShellSort {
    public static void shellSort(int[] array) {
        int h = 1;//序列
        while (h <= array.length / 3)
            h = 3 * h + 1;
        //间隔直到h=1为止
        while (h > 0) {
            for (int i = h; i < array.length; i++) {
                int temp = array[i];
                int pos = i;
                while (pos > h - 1 && array[pos - h] > temp) {
                    array[pos] = array[pos - h];
                    pos -= h;
                }
                array[pos] = temp;
            }
            h = (h - 1) / 3;
        }
    }

    public static void main(String[] args) {
        int []array= Tools.generaterArray(20,20);
        Tools.printIntArray(array);
        shellSort(array);
        Tools.printIntArray(array);
    }
}
